import functools
import collections


class Solution(object):
    def minAbbreviation(self, target, dictionary):
        """
        :type target: str
        :type dictionary: List[str]
        :rtype: str
        """

        @functools.cache
        def search(i, word, n):
            out = collections.defaultdict(int)
            if i == 0:
                j = i
                while j < n - 1:
                    out2 = search(j + 1, word, n)
                    for item in out2:
                        out[str(j - i + 1) + item] = out2[item] + 1
                    j += 1
                out[str(j - i + 1)] = 1
            if i < n - 1:
                j = i
                while j < n - 1:
                    out2 = search(j + 1, word, n)
                    for item in out2:
                        if j - i > 0:
                            out[word[i] + str(j - i) + item] = out2[item] + 2
                        else:
                            out[word[i] + item] = out2[item] + 1
                    j += 1
                if i < n - 1:
                    out[word[i] + str(n - 1 - i)] = 2
            else:
                if i == 0:
                    return {word[n - 1]: 1, '1': 1}
                else:
                    return {word[n - 1]: 1}
            return out
        t_set = search(0, target, len(target))
        for item in dictionary:
            if len(item) == len(target):
                i_set = search(0, item, len(item))
                for w in i_set:
                    if w in t_set:
                        t_set.pop(w)
        if not t_set:
            return ''
        else:
            min_length = len(target) + 1
            for item in t_set:
                if t_set[item] < min_length:
                    t_out = item
                    min_length = t_set[item]
            return t_out


data = Solution()
target = "aaaaaxaaaaa"
dictionary = ["bbbbbxbbbbb"]
print(data.minAbbreviation(target, dictionary))
target = "apple"
dictionary = ["blade"]
print(data.minAbbreviation(target, dictionary))
target = "apple"
dictionary = ["blade","plain","amber"]
print(data.minAbbreviation(target, dictionary))
target = "aaaaaxaaaaa"
dictionary = ["bbbbbxbbbbb"]
print(data.minAbbreviation(target, dictionary))